package queue_stack.leetcode.medium;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author bruin_du
 * @description 栈的压入、弹出序列
 * @date 2022/6/14 22:49
 **/
public class Offer31_ValidateStackSequences {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        //方法一：使用栈模拟
        //时间复杂度:O(n),空间复杂度:O(n)
        method1(pushed,popped);

        //方法二:使用双指针模拟栈
        return method2(pushed,popped);
    }

    private boolean method1(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<>();
        int i = 0;
        for (int num : pushed) {
            stack.offerLast(num);
            while(!stack.isEmpty() && stack.peekLast() == popped[i]) {
                i++;
                stack.pollLast();
            }
        }
        return stack.isEmpty();
    }

    private boolean method2(int[] pushed, int[] popped) {
        int i = 0,j = 0;
        for (int num : pushed) {
            pushed[i] = num;
            while(i >= 0 && pushed[i] == popped[j]){
                i--;
                j++;
            }
            i++;
        }
        return i == 0;
    }
}
